New Grafton is a community in the Canadian province of Nova Scotia, located in the Region of Queens Municipality .